package com.sky.alogrithm.chapter02_sort;

import static com.sky.alogrithm.chapter02_sort.Example.each;
import static com.sky.alogrithm.chapter02_sort.Example.less;

/**
 * 快速排序
 * 原理：将一个数组分成两部分，切分的位置取决于数组的内容，前一部分不大于中间元素，后一部分不小于中间元素
 */
public class Quick {

    public static void sort(Comparable[] a){
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo){
            return;
        }
        //先用partition()方法将a[j]放到一个合适的位置，燃火
        //再用递归调用将其他位置的元素排序
        int j = partition(a, lo, hi); //切分
        sort(a, lo, j - 1); //将左半部分排序
        sort(a, j + 1, hi); //将右半部分排序
    }

    private static int partition(Comparable[] a, int lo, int hi){
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while(true) {
            while (less(a[++i], v)){
                if (i == hi) {
                    break;
                }
           }

            while(less(v, a[--j])){
                if(j == lo){
                    break;
                }
            }

            if(i >= j){
                break;
            }

            each(a, i, j);
        }
        each(a, lo, j);
        return j;
    }

    /**
     * 三向切分的快速排序
     * a[i]小于v，将a[lt]和a[i]交换，将lt和i加一
     * a[i]大于v, 将a[gt]和a[i]交换，将gt减一
     * a[i]等于v, 将i加一
     */
    private static void sort2(Comparable[] a, int lo, int hi){
        if(hi <= lo){
            return;
        }
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while(i <= gt){
            int cmp = a[i].compareTo(v);
            if(cmp < 0){
                each(a, lt++, i++);
            }else if (cmp > 0){
                each(a, i, gt--);
            }else{
                i++;
            }
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
}
